// 给定一个整数n，返回所有不同的 n皇后问题的解决方案，每种解法包含了一个不同的n皇后问题的棋子防止方案
// N皇后问题：将n个皇后放置在n*n的棋盘上，并且使得皇后彼此之间不能攻击
// 皇后彼此不能相互攻击：指的是任何两个皇后都不能处于同一条横线，纵线或者斜线上

function solveNQueue(n) {
    // 棋盘初始化
    let chessboard = new Array(n).fill(1).map(_ => new Array(n).fill('.'))
    // 存放所有符合条件的集合
    let res = []
    // 放置第row行的皇后
    function backtrack(chessboard, row) {
        if (row === n) {
            let path = []
            for (let i = 0; i < chessboard.length; i++) {
                let row_str = chessboard[i].join('')
                path.push(row_str)
            }
            res.push(path)
            return
        }
        // 枚举可放置皇后的列
        for (let col = 0; col < n; col++) {
            // 如果该位置与之前放置的皇后不发生冲突
            if (isValid(n, row, col, chessboard)) {
                // 选择row，col位置放置皇后
                chessboard[row][col] = 'Q'
                // 递归放置row + 1行之后的皇后
                backtrack(chessboard, row + 1)
                // 撤销选择row和col的位置
                chessboard[row][col] = '.'
            }
        }
    }
    backtrack(chessboard, 0)
    return res
}

// 判断当前位置row和col是否与之前放置的皇后发生冲突
function isValid(n, row, col, chessboard) {
    for (let i = 0; i < row; i++) {
        if (chessboard[i][col] === 'Q') {
            return false
        }        
    }

    // 45度斜线
    let i = row - 1
    let j = col - 1
    while (i >= 0 && j >= 0) {
        if (chessboard[i][j] === 'Q') {
            return false
        }
        i -= 1
        j -= 1
    }

    // -45度斜线
    i = row - 1
    j = col + 1
    while (i >= 0 && j < n) {
        if (chessboard[i][j] === 'Q') {
            return false
        }
        i -= 1
        j += 1
    }
    return true
}

console.log(solveNQueue(4));